﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Problems.Geometry;

namespace Demos.Problems
{
    public class ObservableQuickhull
    {
        #region Delegates

        public delegate void Linea(Tuple<double, double> p1, Tuple<double, double> p2, Convexhull.Board algoritmo);

        #endregion

        public event Linea NuevaLinea;

        public IEnumerable<Tuple<double, double>> quickhull(Algoritmia.DataStructures.Lists.IList<Tuple<double, double>> S)
        {
            if (S.Count <= 2)
            {
                return S.ToList();
            }

            var p = S.Min();
            var q = S.Max();

            var z1 = S.Where(i => Comparer<Tuple<double, double>>.Default.Compare(i, p) != 0 &&
                                  Comparer<Tuple<double, double>>.Default.Compare(i, q) != 0 &&
                                  Utils.Left(new Point2D(p), new Point2D(q), new Point2D(i))).ToList();
            var z2 = S.Where(i => Comparer<Tuple<double, double>>.Default.Compare(i, p) != 0 &&
                                  Comparer<Tuple<double, double>>.Default.Compare(i, q) != 0 &&
                                  Utils.Right(new Point2D(p), new Point2D(q),new Point2D(i))).ToList();

            var z3 = new ArrayList<Tuple<double, double>>(z1);
            var z4 = new ArrayList<Tuple<double, double>>(z2);

            return _quickhull(p, z3, q).Concat(_quickhull(p, z4, q));
        }

        private IEnumerable<Tuple<double, double>> _quickhull(Tuple<double, double> p, Algoritmia.DataStructures.Lists.IList<Tuple<double, double>> A, Tuple<double, double> q)
        {
            if (A.Count == 0)
            {
                return new ArrayList<Tuple<double, double>> {p, q};
            }

            var h = new Tuple<double, double>(0, 0);
            double maxArea = 0;
            foreach (var z in A)
            {
                var area = Utils.TriangleArea(new Point2D(p), new Point2D(q), new Point2D(z));
                if (area > maxArea)
                {
                    maxArea = area;
                    h = z;
                }
            }

            var z1 = A.Where(z => Utils.Left(new Point2D(p), new Point2D(h), new Point2D(z))).ToList();
            var z2 = A.Where(z => Utils.Right(new Point2D(p), new Point2D(h), new Point2D(z))).ToList();

            var z3 = new ArrayList<Tuple<double, double>>(z1);
            var z4 = new ArrayList<Tuple<double, double>>(z2);

            return _quickhull(p, z3, h).Concat(_quickhull(h, z4, q));
        }
    }
}